世新大學九十三學年度碩博士班考試試題卷

學 系 別	考 試 科 目
資訊管理學系資訊科技組	離散數學

※考生請於答案卷內作答

1. (15points, 5 points each)

Prove the following formulas, where denotes the number of combinations of size from a collection of size with 0.

(a) , for each integer n>0

(b) , for each integer n>0

(c)

2. (10 points)

Prove that 1³+2³+…+n³ = (1+2+…+n)² for each integer n>0.

3. (10points)

Solve the recurrence relation b_n+1=3b_n, n0, b₀ =3.

4. (20points)

Prove the following properties about graphs and trees.

(a) If u and v are distinct vertices in a tree T=(V,E), then there is a unique path connecting u and v. (6points)

(b) If G =(V,E) is an undirected simple graph, then G is connected if and only of G has a spanning tree. (6 points)

(c) In every tree T =(V,E), (8 points)

5. (15 points, 5 points each)

Draw the Hasse diagrams for the following four posets (partially ordered sets).

(a) and A=P(U)(the powerset of U) with R is the subset relation on A.

(b) and R is the “exactly divides” relation applied on A.

(c) Prove that the relation R in (b) is a total order on A.

6. (10points, 5points each)

Let A and B be two nonempty finite sets with and .

(a) What is the total number of functions from A to B.

(b) What is the total number of one-to –one functions from A to B. (assume that )

7. (10 points)

Prove that where A₁ are nonempty sets, .

8. (10 points)

A teacher has thirteen discrete mathematics textbooks. Seven textbooks are written by Dr. K and six textbooks are written by Dr. Y. In how many ways he can distribute the thirteen textbooks among four students so that each student receives at least one textbook written by Dr. K.